package com.leetcode.search.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/26 22:22
 */
public class Combine_77 {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (n == 0 || k == 0) return res;
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(1, n, k, track);
        return res;
    }

    private void backtrack(int start, int n, int k, LinkedList<Integer> track) {
        if (track.size() == k) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i <= n; i++) {
            track.add(i);
            // 每次传入下一位
            backtrack(i + 1, n, k, track);
            track.removeLast();
        }
    }

}
